/*
 * @lc app=leetcode.cn id=1562 lang=typescript
 *
 * [1562] 查找大小为 M 的最新分组
 */

// @lc code=start

class Union {
  data: number[];
  size: number[];
  cnt: number[];
  constructor(n: number) {
    this.data = new Array(n + 1);
    this.size = new Array(n + 1);
    this.cnt = new Array(n + 2).fill(0);
    this.cnt[1] = n + 1;
    for (let i = 0; i <= n; i++) {
      this.data[i] = i;
      this.size[i] = 1;
    }
  }
  find(x: number) {
    if (this.data[x] === x) return x;
    return (this.data[x] = this.find(this.data[x]));
  }
  merge(x: number, y: number) {
    let rx = this.find(x);
    let ry = this.find(y);
    if (rx === ry) return;
    if (this.size[rx] > this.size[ry]) {
      [rx, ry] = [ry, rx];
    }
    this.data[rx] = ry;
    this.cnt[this.size[rx]]--;
    this.cnt[this.size[ry]]--;
    this.size[ry] += this.size[rx];
    this.cnt[this.size[ry]]++;
  }
}

function findLatestStep(arr: number[], m: number): number {
  const n = arr.length;
  const union = new Union(n);
  let ans = -1;
  for (let i = 0; i < n; i++) {
    union.merge(arr[i], arr[i] - 1);
    if (union.cnt[m + 1]) ans = i + 1;
  }

  return ans;
}
// @lc code=end
